package com.heima.leetcode.datastructure.priorityqueue;

import com.heima.leetcode.datastructure.linkedlist.ListNode;

/**
 * 合并多个升序链表 23
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/3 20:06
 */
public class MergeMulAscLinkedList {
    // 1、假设有k个链表，那么用k个指针指向各个链表头节点
    // 2、指针先都往后移动一位，就插入k个头节点到优先级队列中去，
    // 3、然后poll一个优先级最高的头节点出来加到新链表中，并把该头节点的next节点插入优先级队列中，如果该头节点的next节点为空了，就继续循环
    // 4、就这样出队一个节点后马上入队刚出队的节点的下一个节点，就能保证优先级队列中的都是剩下节点中val最小的的k个节点
    // 5、因为优先级取决于节点值的大小，越小优先级越高，所以用小顶堆实现优先级队列
    public static ListNode mergeKLists(ListNode[] lists){
        ListNodePriorityQueue queue = new ListNodePriorityQueue(lists.length);
        ListNode sentinel = new ListNode(-1,null);
        // 把头节点都放入优先级队列
        for (ListNode list : lists) {
            if (list != null){
                queue.offer(list);
            }
        }
        ListNode p = sentinel;
        // poll一个节点出来，再把下一个节点offer进去，就可以达成优先级队列里面永远是剩下节点里面val值最小的k个节点，k为链表个数
        while (!queue.isEmpty()){
            ListNode node = queue.poll();
            if (node.next != null){
                queue.offer(node.next);
            }
            // 加到新链表中
            p.next = node;
            p = p.next;
        }
        return sentinel.next;
    }
}
